1. Field of the Invention
This invention describes a sequential coding system which converts unconstrained data into a constrained format in an invertible manner. The described invention is particularly useful in dynamic memory systems.
2. Description of the Prior Art
Various ways have been proposed in the past for increasing the recorded data density on mediums such as magnetic discs or tapes and in other similar media. One approach utilized is known as run-length-limited coding which requires that each "1" in a coded bit sequence must be separated from the nearest adjacent "1" by a specified number of "0's". This number must be at least equal to a minimum quantity d because of intersymbol interference but must not exceed a maximum of k which is required for self-clocking purposes. Codes following this format are generally referred to as (d,k) run-length-limited codes. The present invention relates to a particular code suited for magnetic recording channels wherein d=2 and k=7. To convert unconstrained data into a (d,k)-constrained format generally requires that m unconstrained bits be mapped into n constrained bits, where m&lt;n. The ratio m/n is usually referred to as the coding rate or efficiency. It is obviously desirable to maximize this rate. The tradeoffs usually considered in maximizing the rate are the decoding look-ahead and the hardware complexity.
Raising the coding efficiency or rate at the expense of decoding look-ahead generally results in increasing the error propagation. That is, a single bit error introduced in the code stream will cause a certain number of subsequent bits to also be erroneous before the coding algorithm becomes self-correcting. It is always desirable to minimize error propagation. It has been found that a coding rate of 1/2 is optimal for the (2,7) code.
U.S. Pat. No. 3,689,899 to P. A. Franaszek discloses two possible (d,k) codes (1,8) and (2,7). The potential data codes are variable length, fixed rate state independent block codes. The coding rate of the (1,8) code is 2/3 and its code dictionary consists of 16 code words whose lengths vary from 3 to 9 bits, in multiples of 3. The (2,7) code has a coding rate of 1/2 and its dictionary consists of seven words with lengths varying from 4 bits to 8 bits, in multiples of 2.
U.S. Pat. No. 4,146,909 of Beckenhauer et al, discloses a (2,7) RLL code having a 1/2 coding rate. This patent differs from the present coding system in two major respects. First, it utilizes a table look-up coding system rather than hardware. Second, while maintaining an overall rate 1/2, it codes variable length unconstrained input vectors into corresponding variable length constrained channel vectors e.g., 1 bit into 2 bits, 2 bits into 4 bits, 3 bits into 6 bits, etc. While the coding methods described in these references will produce codes having the same (d,k) values as the herein disclosed code and the same coding rate 1/2, the actual coding tables will be substantially different and the coding method differs in a number of respects.
The (2,7) code constructed by Franaszek has a variable length look-ahead encoder and a variable length decoder. The encoder converts one data bit into 2 constrained bits by employing a variable length look-ahead of, at most, two additional data bits. The coded output is thus a function of the present and the future one or two data bits. The decoder maps two constrained bits into one data bit as a function of the present channel state, at most one future channel state and at most two previous channel states. A channel error will not propagate beyond three decoded data bits.